/**
 * 版权所有 2009-2012山东新北洋信息技术股份有限公司
 * 保留所有权利。
 */
package com.linyaonan.leetcode.medium._24_new;

import java.util.List;

/**
 *
 * 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
 *
 * 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
 *
 *  
 *
 * 示例:
 *
 * 给定 1->2->3->4, 你应该返回 2->1->4->3.
 *
 *
 * @ProjectName: leetcode
 * @Package: com.linyaonan.leetcode.medium._24_new
 * @ClassName: SwapPairs
 * @Author: linyaonan
 * @Date: 2020/3/26 11:04
 */
public class SwapPairs {

    public ListNode swapPairs(ListNode head) {
        // 异常处理
        if (head == null) {
            return null;
        }
        ListNode org = new ListNode(-1);
        org.next = head;
        ListNode realHead = org;
        int startIndex = 0;
        while (head != null) {
            // 偶数位
            if (startIndex % 2 == 0) {
                // 保存下一位
                ListNode pre = head.next;
                if (head.next != null) {
                    head.next = head.next.next;
                }
                if (pre != null) {
                    pre.next = head;
                    realHead.next = pre;
                    head = pre;
                }
            }
            head = head.next;
            realHead = realHead.next;
            startIndex++;
        }

        return org.next;
    }

    /**
     * 题目要求原地交换，所以抽取一个函数
     * @param head
     * @return
     */
    public ListNode swapPairs2(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode r = new ListNode(-1);
        ListNode tt = r;
        while (head != null && head.next != null) {
            head = re(head);
            r.next = head;

            head = head.next.next;
            r = r.next.next;
        }
        return tt.next;
    }

    /**
     * 将链表的前两个数据进行原地交换
     * 1. 如果链表数据不足两个则不交换
     * 2. 如果满足两个
     * @param h
     * @return
     */
    public ListNode re(ListNode h) {
        // 1. 异常情况不交换
        if (h == null || h.next == null) {
            return h;
        }

        // 2. 交换前两个数据
        ListNode p2 = h.next;
        ListNode n = h.next.next;

        p2.next = h;
        h.next = n;
        return p2;
    }

}
